package com.ztom.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * 和为 K 的子数组
 * <p>
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/
 *
 * @author ZhangTao
 */
public class Code95SubarraySum {

    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 记录当前位置前缀和
        int pre = 0;
        // 记录当前位置前缀和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int count = 0;
        for (int num : nums) {
            pre += num;
            // 如果存在前缀和 + 当前前缀和 = k
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}
